COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	NCOMPL	- The MACLISP Number COMPiLeR
C00007 00003	A User's Guide to the Fast Arithmetic Feature of the Lisp Compiler
C00008 00004	1- Introduction
C00011 00005	2- Number Variables 
C00016 00006	3- Declaring functions
C00020 00007	4- Scope of declarations
C00023 00008	5- Open-coding arithmetic expressions
C00029 00009	6- Arrays
C00031 00010	7- Miscellany
C00032 ENDMK
C⊗;
NCOMPL	- The MACLISP Number COMPiLeR

	The MACLISP compiler is called NCOMPLR  (for Number COMPiLeR)
and  is noted for  being the  "best" LISP  compiler in  existence. In
particular there are facilities for declaring the types of objects so
that a  fair amount of  open-coding is  possible; this is  especially
nice for numerical  computations (hence the "N" in NCOMPLR). For more
information on this either locate an old MACLISP manual or ask RPG or
WLS.
	To compile a file do:
		R NCOMPLR
		<target>←FN.EXT<(SWITCHES)>

The <target>  is optional  and defaults  accordding to the  switches.
Briefly the switches are:
	T 	Talk: verbose mode
	A	Assemble: take a .LAP file and assemble it
	F	Fasload: take a source file and compile & assemble it
	K  	Kill: take a source file and compile & assemble it but 
		kill the LAP file
The default names  are FN.LAP for a  compiled file and FN.FAS  for an
assembled file.  NCOMPLR understands ALIASes.
	One can inform the compiler about one's intentions by placing
DECLARATIONs in the file. DECLARATIONs are of the form:
		(DECLARE <decl1><decl1>...<decln>)
The compiler actually evauates each of the <decli>'s so
that (DECLARE (EVAL (READ))) is meaningful.
Some important other declarations are:

(SPECIAL var1 var2 ...) Says that var1, var2, etc are special

(UNSPECIAL var1 var2 ...) Says that var1, var2, etc are local

(*EXPR fn1 fn2 ..) fn1, fn2 etc are EXPRs

(*LEXPR fn1 ...) fn1 etc are LEXPRs

(*FEXPR fn1 ...) fn1 etc are FEXPRs

(**ARRAY arr1 ...) arr1 etc are arrays

(FIXNUM v1 ...) v1 etc are fixnums

(FLONUM v1 ...) v1 etc are flonums

(FIXNUM (fn1 type1 ...) ...) fn1 etc returns a fixnum and its arguments are
			     of the type specified.

(FLONUM (fn1 type1 ...) ...) as above

(NOTYPE v1 (fn1 type1 ...) ...) v1, fn1, etc have no type

(FIXSW T) all arithmetic is FIXNUM except that denoted by +$ etc

(FLOSW T) all arithmetic is FLONUM except that denoted by + etc

(FIXSW NIL)(FLOSW NIL) shuts off above

(SETQ SPECIAL T) all variables are special

(SETQ NFUNVARS T) no functional values allowed

(MACROS T) causes macros to be defined at runtime as well as compile time

(MACROS NIL) shuts off above

(GENPREFIX foo) causes auxilliary functions generated by the compiler to be
		named foon etc.

(ARRAY* (type arr1 n1 arr2 n2 ...)...) says that arr1, arr2 etc are of type type
				       and  that arr1 is n1 dimensional etc.

(ARITH (type1 fn1 ...) ...) says to replace a general arithmetic function with
			    a one-type function. Thus (ARITH (FIXNUM PLUS))
			    will replace occurrences of PLUS with +.

(MAPEX T) open code MAP type functions

(NOARGS T) suppress number-of-args information (saves space)

(MESSIOC chars) does (IOC chars), used for suppressing error messages or
	        directing them to the LAP file

(MUZZLED T) suppresses closed-compilation messages
A User's Guide to the Fast Arithmetic Feature of the Lisp Compiler



							  Eric Rosen
							     4/25/72

1- Introduction

The fast-arithmetic feature of NCOMPLR attempts to take advantage of the
new uniform representation of numbers in NLISP by open-coding arithmetic
expressions, i.e.  by generating machine instructions to do arithmetic, in
lieu of generating calls to LISP's arithmetic functions.  It will also
generate compare or conditional jump instructions in lieu of calls to
MINUSP, ZEROP, PLUSP, GREATERP, LESSP, SIGNP, and for numeric arguments,
EQUAL.  In order to facilitate this, the user MUST make declarations to
the compiler, so the compiler knows which of the user's functions and
variables have numerical values, and whether these values are fixnum or
flonum.  The compiler introduces a new data type which has no analogue in
the interpreter, i.e.  number quantities.  A number quantity is merely a
machine number.  A LISP number is actually a pointer to a word in
garbage-collectable FIXNUM or FLONUM space which contains a machine
number; a number quantity is a machine number itself, with no intervening
pointer.  The compiler will automatically handle the intermediate results
of open-coded arithmetic expressions as number quantities.  Also, by
suitable use of declarations, the user may inform the compiler that
certain of his variables are to be treated as number quantities.  Number
quantities are not stored in garbage-collectable space, but on the FIXNUM
or FLONUM PDLs.

Open compilation is, of course, only relevant to single- word arithmetic.
Those users who wish to utilitize infinite- precision integer arithmetic
(BIGNUMS) MUST close-compile their code.

2- Number Variables 

The following declarations enable the user to tell the ccmpiler which of
his variables are always going to have either fixnum or flonum values, and
whether these values are fixed or floating point:

	    (DECLARE (FIXNUM XVAR1 XVAR2 ...  XVARn)
		     (FLONUM LVAR1 LVAR2 ...  LVARn))

In the case of local variables (i.e.  variables which have not been
declared or made special) these declarations indicate that the value of
the variable is a number quantity.  In the case of special variables,
these declarations indicate to the compiler that the value of the variable
is a LISP number of the given type.  (For technical reasons, no special
variable can have a number quantity as its value.)

It is important to realize that number variables, i.e.  variables whose
values are number quantities, do not exist in the interpreter.  Thus a
number variable is not a LISP variable in the usual sense, and there are
restrictions on its use.  A NUMBER VARIABLE MAY NEVER HAVE ANY OTHER VALUE
THAN A NUMBER.  Furthermore, a fixnum number variable may never have a
flonum value, and vice versa.  If these restrictions are ignored, errors
will result.  The compiler will try to detect such errors, but most of
them cannot be detected at compile time.  Thus the user must be very
careful to pay heed to these restrictions.  FAILURE TO DO SO WILL MEAN
THAT CODE WHICH MAY RUN PERFECTLY WELL UNDER THE INTERPRETER WILL RUN
ERRONEOUSLY WHEN COMPILED.  The user should be particularly careful with
PROG variables that are also number variables.  The interpreter
initializes all PROG variables to NIL.  However, since number variables
may not have the value NIL, the compiler initializes number PROG variables
to 0 or 0.0.  Because of this inconsistency with the interpreter, IT IS AN
ERROR TO USE NUMERIC PROG VARIABLES BEFORE INITIALIZING THEM.  Again, the
compiler will try to detect these errors, but will not always be able to.

It is, of course, permissible to SETQ or LAMBDA-bind number variables to
any expression whose value is a number, be it a number quantity or a LISP
number.  It is also permissible to SETQ or LAMBDA-bind LISP variables to
number variables.  In all cases the compiler will cause the correct
conversion to be done.

It should be realized that if a number quantity is ever CONS'd into a list
structure, it will have to first be converted into a LISP number.  This is
relatively expensive in time, because repeated number CONSing will cause
more frequent garbage collections.  The compiler makes every effort to
avoid number CONSing, and therefore number CONSing is done only when
absolutely necessary.  However if the user keeps any numerical parameters
for the purpose of CONSing them into lists, he may be better off making
them regular LISP variables.  (Parameters which are to be used in
arithmetic computation are, of course, best kept in number variables.)

The following declaration is available for negating the effect of previous
FIXNUM or FLONUM declarations:

	    (DECLARE (NOTYPE VAR1 VAR2 ...  VARn))

3- Declaring functions

The following declarations are available for declaring functions to the
compiler:

	(DECLARE (FIXNUM (XFN1 ARG1 ...   ARGn) ...   (XFNm ARG1 ...  ARGn)) 
		 (FLONUM (LFN1 ARG1 .. .  ARGn) .. .  (LFNm ARG1 ...  ARGn)) 
		 (NOTYPE (NFN1 ARG1 ...   ARGn) ...   (NFNm ARG1 ...  ARGn)))

Of course, variable declarations may be intermingled with function
declarations as in:

	(DECLARE (FIXNUM VAR1 VAR2 (FN FIXNUM NOTYPE)))

The arguments to these FIXNUM, FLONUM, and NOTYPE declarations are lists.
The CAR of each list is the name of the function being declared.  The CDR
of each list is a list of the types of the arguments of the functions,
where each argument type is either 'FIXNUM' (or, as an abbreviation, any
fixnum number), 'FLONUM' (or any flonum number), or 'NOTYPE' (or 'NIL').
The main declaration tells what kind of value the function returns.  Hence
these declarations have the effect of both declaring what kinds of
arguments the function takes, and what kind of value it returns.

For example, suppose function FOO returns a floating point number.
Further, suppose FOO has three arguments - a fixed-point number, a random
list, and a floating point number.  The appropriate declaration is:

	(DECLARE (FLONUM (FOO FIXNUM NOTYPE FLONUM)))

Suppose BAR is just like FOO, except that its value is not numeric.  The
appropriate declaration is:

	(DECLARE (NOTYPE (BAR FIXNUM NOTYPE FLONUM)))

Arguments may be omitted on the right, in which case NOTYPE is assumed.
For instance, if FOOBAR has three arguments , the following two
declarations are completely equivalent:

	(DECLARE (FIXNUM (FOOBAR FLONUM NOTYPE NOTYPE)))
and 
	(DECLARE (FIXNUM (FOOBAR FLONUM)))

THE SAME DECLARATION MUST BE IN FORCE WHEN A FUNCTION IS COMPILED AS WHEN
A CALL TO THAT FUNCTION IS COMPILED.  If this rule is not followed, the
functions may not interface properly, causing random results and/or LISP
errors.  Compiled functons should interface properly with uncompiled
functions , however, regardless of declaratons.

4- Scope of declarations

Declarations are either global, or local to the nearest- enclosing PROG or
LAMBDA in which they appear.  If a declaration occurs which is not within
a function definition, it is global.  It maintains its effects until
countermanded by some other global declaration or temporarily overridden
by a local declaration.  Local declarations should always appear as the
first statements of the PROG or LAMBDA in which they occur.  They affect
only the PROG or LAMBDA in which they occur, and they take precedence over
any conflicting global or superior (in position) local declarations.

When a function declaration is used to declare the arguments of the
function, the scope is just the function in question.

Only FIXNUM, FLONUM, and NOTYPE declarations are legal as local
declarations.  All other declarations must be global, i.e. they cannot
appear within a function body.  It is not legal to locally undeclare a
variable (i.e.  by using the NOTYPE declaration).  The only use of local
function declarations is to declare bound variable functions.  For
example, where 'X' is a bound variable the declaration

	(DECLARE (FIXNUM (X FIXNUM)))

means that 'X' is bound to a function whose first (perhaps only) argument
is a fixnum and which returns a fixnum value.  In order for this
declaration to work properly, all the functions to which 'X' may be bound
must have been so declared when they were compiled.

5- Open-coding arithmetic expressions

The compiler is able to open-code the following arithmetic functions:
PLUS, TIMES, DIFFERENCE, *DIF, QUOTIENT, *QUO, ADD1, SUB1, REMAINDER,
MINUS, ABS, FIX, FLOAT, MINUSP, PLUSP, SIGNP, BOOLE, ROT, LSH, GREATERP,
LESSP, and if its arguments are numeric, EQUAL.

	(DECLARE (CLOSED  T))

inhibits  open-coding.

	(DECLARE (CLOSED  NIL))

enables it, and is the default option.  If the compiler cannot figure out
whether the arguments to the above functions are fixnums or flonums, it
will be forced to generate a call to the appropriate routine in the
interpreter.  The compiler makes use of the user's declarations to
determine the types of the arguments.  When the compiler encounters an
expression with an argument whose type it can not determine, it tries to
open-compile as much of the expression as it can.  If an expression has to
be even partially closed-compiled the compiler will print a warning
message.  This message is expected to be of aid to users who would like
open-compiling but who aren't getting it because they forgot to make a
declaration.  However, users who want some expressions to be
closed-compiled may want to inhibit this message by saying
	(DECLARE (MUZZLED T)).

The compiler also offers the user other ways to force open-compilation.
If the user says (DECLARE (FIXSW T)) , the compiler will assume that all
arguments to open-codable functions (except, of course, EQUAL) are
fixnums.  Similarly, the user can (DECLARE (FLOSW T)) if he is only using
flonums.  The LISP functions + , - , * , / , | , 1+ , 1- , are just like
PLUS , DIFFERENCE, TIMES, QUOTIENT, REMAINDER, ADD1, and SUB1 except that
the former may take only fixnum arguments.  Therefore the compiler is able
to always open-code the former.  Similarly, the LISP functions +$, -$, *$,
/$, 1+$, and 1-$ (these are real dollar signs, not alt.  modes) may take
only flonum arguments, and are always open-coded.  The predicates >, <,
and = are also always open-coded; they correspond to GREATERP, LESSP, and
EQUAL except that they always have two numerical arguments of the same
type.  (In these last 3 cases, the compiler need not know which type the
arguments are).  The third way to force open-coding is by means of the
ARITH declaration.  The declaration (DECLARE (ARITH (FIXNUM ADD1 SUB1)
(FLONUM QUOTIENT))) effectively causes all SUB1's to be replaced by 1-'s,
ADD1's by 1+'s, and QUOTIENTS by /$'s.  To revert back to normal (DECLARE
(ARITH (NOTYPE ADD1 SUB1 QUOTIENT))).

These techniques just described are NOT a substitute for declaring
variables and functions.  They are useful in cases where the compiler will
not be able to determine the type of an argument, for instance (PLUS (CAR
X) (CADR X)).  Obviously the compiler has no way of knowing that (CAR X)
is going to be a fixnum.  So in a case like this, there is a definite
advantage to using + instead of PLUS.  And if all the user's arithmetic is
in the same mode, a FIXSW or FLOSW declaration may be good for him.  If a
(FIXSW T) declaration is made, the only way to do any flonum arithmetic at
all is to use a function which assumes that its arguments are flonums,
e.g. +$.

6- Arrays

The user should always declare his arrays to the compiler.  The ARRAY*
declaration is available for this purpose.  (Note that 'ARRAY*' is not
'*ARRAY; the latter is a LISP function).  For instance,

	(DECLARE (ARRAY* (FIXNUM FOO 1 BAR 2)
			 (FLONUM ARY 3)
			 (NOTYPE FOOBAR 1 ARY2 2))) 

This declares FOO to be a 1-dimensionsal array of fixnums, BAR a
2-dimensional array of fixnums, ARY a 3-dimensional array of flonums,
FOOBAR a 1-dimensional array of random S-expressions, and ARY2 a
2-dimensional array of S-expressions.  Undeclared arrays will be handled
properly, but at great loss of efficiency.  It should be understood that
arrays cannot [currently] contain machine numbers - only LISP
s-expressions, including LISP numbers, are permitted.  However, by the end
of calendar year 1973, there will be two new types of arrays implemented
in LISP, the FIXNUM array and the FLONUM array, which will in fact contain
machine numbers of the stated type.  Accessing the elements of such arrays
will be open-coded by NCOMPLR, and the resultant code should be
speed-competitive with FORTRAN array accessing [except that there are no
plans for implementing the hairier optimizations done by really good
FORTRAN compilers}.

7- Miscellany

The fast-arithmetic compiler is loaded by 'R NCOMPLR', but all other
interactions with it are exactly the same as with complr [command line
parsing, compilations switches, etc.].

The code it produces runs only in LISPs with version number greater than
400.

For general information on LISP, see Lisp Archiv.

Any bugs in the NCOMPLR should be reported to Eric Rosen (ECR) or Jonl
White (JONL).